import java.util.Arrays;

public class 兑换零钱问题 {
    
    public static void main(String[] args) {
        

        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }

    public static int coinChange(int[] coins, int amount) {

        // 0-1 背包问题
        int[] f = new int[amount + 1]; // f[i] 表示凑齐 i 所需的最少硬币数量

         Arrays.fill(f, Integer.MAX_VALUE); // 初始化
        f[0] = 0;

        for (int coin : coins) { // 遍历 weight
            for (int i = coin; i <= amount; i++) { // 遍历 value
                if (f[i - coin] == Integer.MAX_VALUE) { // 还未计算不使用该硬币的情况
                    continue;
                }
                f[i] = Math.min(f[i], f[i - coin] + 1); // 是否使用该硬币，value = 1
            }
        }

        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }
}
